/*
*
给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 32 + 12 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。
示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 41 = 4 。
- n = 31 + 11 = 4 。

提示：

1 <= n <= 300
1 <= x <= 5

  - @author ala
  - @date 2024-09-30 16:51
*/
package main

import "fmt"

func main() {
	n, x := 10, 2
	fmt.Println(numberOfWays(n, x))
}

func numberOfWays(n int, x int) int {
	nums := make([]int, 0, n)
	i, pi := 0, 0
	for pi <= n {
		i++
		pi = quickPow(i, x)
		if pi > n {
			break
		}
		nums = append(nums, pi)
	}

	dp := make([]int, n+1)
	dp[0] = 1
	for _, _n := range nums {
		for i := n; i >= _n; i-- {
			dp[i] = (dp[i] + dp[i-_n]) % MOD
		}
	}
	return dp[n]
}

var MOD int = 1e9 + 7

func quickPow(n, x int) int {
	if x == 1 {
		return n
	}
	m := quickPow(n, x>>1)
	if x&1 == 1 {
		return m * m * n
	} else {
		return m * m
	}
}
